/* UNIVERSIDADE FEDERAL DE CAMPINA GRANDE - UFCG
 * Disciplina: Laboratorio de Estrutura de Dados
 * Professor: Marco Aurelio Spohn
 * Alunos: Alexandre Sales Vasconcelos       Mat.: 20621146
 * Atividade 5
 */

/**
 * Implementar o algoritmo de ordenacao HeapSort.
 * 
 * @version 1.0 2008/05/19
 * @author Alexandre Sales Vasconcelos
 * @see <a href="http://lab.eda.ufcg.googlepages.com/ordenacaoheap"> Atividade 5 Problema 1</a>
 */
public class HeapSort {

	int[] vetor;

	/**
	 * Metodo para ordena uma array tipo int.
	 * 
	 * @param lista um array tipo int.
	 */
	public void HeapSortOrdenacao(int[] lista) {
		
		heapMax(lista);
		swap(lista, 0, lista.length-1);
		for (int i=lista.length-2; i>0; i--) {
			heapTest(lista, 0, i);
			swap(lista, 0, i);
		}
		vetor = lista;
	}
	
	/**
	 * Metodo que verifica se o filhos tem valor maior que o pai, fazendo
	 * o swap em caso afirmativo.
	 * 
	 * @param lista Array tipo int que sera verificado
	 * @param raiz informa a posicao da raiz no Array
	 * @param fim define o tamanho do array.
	 */
	private void heapTest(int[] lista, int raiz, int fim) {
		
		int left = raiz*2+1;
		int right = raiz*2+2;
		
		if (right <= fim) {
			if (lista[raiz] < lista[left] || lista[raiz] < lista[right]) {
				if (lista[left] > lista[right]) {
					swap(lista, raiz, left);
					heapTest(lista, left, fim);
				} else {
					swap(lista, raiz, right);
					heapTest(lista, right, fim);
				}
			}
		} else if (left <= fim) {
			if (lista[raiz] < lista[left]) {
				swap(lista, raiz, left);
				heapTest(lista, left, fim);
			}
		}
	}

	/**
	 * Metodo verifica as condicoes do heap estao satisfeita
	 * 
	 * @param lista o Array que sera colocado no modo heap.
	 */
	private void heapMax(int[] lista) {
		for (int i=(lista.length)/2-1; i>=0; i--) {
			heapTest(lista, i, lista.length-1);
		}
	}
	

	/**
	 * Metodo que realiza a troca de posicao dos elementos no Array
	 * 
	 * @param lista Array com os elementos a serem trocados
	 * @param pos1 elemento que ira para posicao 2
	 * @param pos2 elemento que ira para posicao 1
	 */
	private void swap(int[] lista, int pos1, int pos2) {
		int temp;
		temp = lista[pos1];
		lista[pos1] = lista[pos2];
		lista[pos2] = temp;
	}
	
	/**
	 * Metodo que retorna uma String com o vetor formatado.
	 * 
	 * @return Uma String com o vetor formado.
	 */
	public String toString() {
		String temp = "";
		for (int i=0; i<vetor.length; i++) {
			temp += vetor[i] + " ";
		}
		return temp.trim();
	}

}
